/*
 * @(#)Area.java	1.21 06/02/24
 *
 * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */

package org.loon.framework.android.game.core.geom;

import java.util.Vector;
import java.util.Enumeration;
import java.util.NoSuchElementException;

/**
 * An <code>Area</code> object stores and manipulates a resolution-independent
 * description of an enclosed area of 2-dimensional space. <code>Area</code>
 * objects can be transformed and can perform various Constructive Area Geometry
 * (CAG) operations when combined with other <code>Area</code> objects. The CAG
 * operations include area {@link #add addition}, {@link #subtract subtraction},
 * {@link #intersect intersection}, and {@link #exclusiveOr exclusive or}. See
 * the linked method documentation for examples of the various operations.
 * <p>
 * The <code>Area</code> class implements the <code>Shape</code> interface and
 * provides full support for all of its hit-testing and path iteration
 * facilities, but an <code>Area</code> is more specific than a generalized path
 * in a number of ways:
 * <ul>
 * <li>Only closed paths and sub-paths are stored. <code>Area</code> objects
 * constructed from unclosed paths are implicitly closed during construction as
 * if those paths had been filled by the <code>Graphics2D.fill</code> method.
 * <li>The interiors of the individual stored sub-paths are all non-empty and
 * non-overlapping. Paths are decomposed during construction into separate
 * component non-overlapping parts, empty pieces of the path are discarded, and
 * then these non-empty and non-overlapping properties are maintained through
 * all subsequent CAG operations. Outlines of different component sub-paths may
 * touch each other, as long as they do not cross so that their enclosed areas
 * overlap.
 * <li>The geometry of the path describing the outline of the <code>Area</code>
 * resembles the path from which it was constructed only in that it describes
 * the same enclosed 2-dimensional area, but may use entirely different types
 * and ordering of the path segments to do so.
 * </ul>
 * Interesting issues which are not always obvious when using the
 * <code>Area</code> include:
 * <ul>
 * <li>Creating an <code>Area</code> from an unclosed (open) <code>Shape</code>
 * results in a closed outline in the <code>Area</code> object.
 * <li>Creating an <code>Area</code> from a <code>Shape</code> which encloses no
 * area (even when "closed") produces an empty <code>Area</code>. A common
 * example of this issue is that producing an <code>Area</code> from a line will
 * be empty since the line encloses no area. An empty <code>Area</code> will
 * iterate no geometry in its <code>PathIterator</code> objects.
 * <li>A self-intersecting <code>Shape</code> may be split into two (or more)
 * sub-paths each enclosing one of the non-intersecting portions of the original
 * path.
 * <li>An <code>Area</code> may take more path segments to describe the same
 * geometry even when the original outline is simple and obvious. The analysis
 * that the <code>Area</code> class must perform on the path may not reflect the
 * same concepts of "simple and obvious" as a human being perceives.
 * </ul>
 * 
 * @since 1.2
 */
@SuppressWarnings({ "unchecked", "rawtypes" })
public class Area implements Shape, Cloneable {
	private static Vector EmptyCurves = new Vector();

	private Vector curves;

	/**
	 * Default constructor which creates an empty area.
	 * 
	 * @since 1.2
	 */
	public Area() {
		curves = EmptyCurves;
	}

	/**
	 * The <code>Area</code> class creates an area geometry from the specified
	 * {@link Shape} object. The geometry is explicitly closed, if the
	 * <code>Shape</code> is not already closed. The fill rule (even-odd or
	 * winding) specified by the geometry of the <code>Shape</code> is used to
	 * determine the resulting enclosed area.
	 * 
	 * @param s
	 *            the <code>Shape</code> from which the area is constructed
	 * @throws NullPointerException
	 *             if <code>s</code> is null
	 * @since 1.2
	 */
	public Area(Shape s) {
		if (s instanceof Area) {
			curves = ((Area) s).curves;
		} else {
			curves = pathToCurves(s.getPathIterator(null));
		}
	}

	private static Vector pathToCurves(PathIterator pi) {
		Vector curves = new Vector();
		int windingRule = pi.getWindingRule();
		// coords array is big enough for holding:
		// coordinates returned from currentSegment (6)
		// OR
		// two subdivided quadratic curves (2+4+4=10)
		// AND
		// 0-1 horizontal splitting parameters
		// OR
		// 2 parametric equation derivative coefficients
		// OR
		// three subdivided cubic curves (2+6+6+6=20)
		// AND
		// 0-2 horizontal splitting parameters
		// OR
		// 3 parametric equation derivative coefficients
		double coords[] = new double[23];
		double movx = 0, movy = 0;
		double curx = 0, cury = 0;
		double newx, newy;
		while (!pi.isDone()) {
			switch (pi.currentSegment(coords)) {
			case PathIterator.SEG_MOVETO:
				Curve.insertLine(curves, curx, cury, movx, movy);
				curx = movx = coords[0];
				cury = movy = coords[1];
				Curve.insertMove(curves, movx, movy);
				break;
			case PathIterator.SEG_LINETO:
				newx = coords[0];
				newy = coords[1];
				Curve.insertLine(curves, curx, cury, newx, newy);
				curx = newx;
				cury = newy;
				break;
			case PathIterator.SEG_QUADTO:
				newx = coords[2];
				newy = coords[3];
				Curve.insertQuad(curves, curx, cury, coords);
				curx = newx;
				cury = newy;
				break;
			case PathIterator.SEG_CUBICTO:
				newx = coords[4];
				newy = coords[5];
				Curve.insertCubic(curves, curx, cury, coords);
				curx = newx;
				cury = newy;
				break;
			case PathIterator.SEG_CLOSE:
				Curve.insertLine(curves, curx, cury, movx, movy);
				curx = movx;
				cury = movy;
				break;
			}
			pi.next();
		}
		Curve.insertLine(curves, curx, cury, movx, movy);
		AreaOp operator;
		if (windingRule == PathIterator.WIND_EVEN_ODD) {
			operator = new AreaOp.EOWindOp();
		} else {
			operator = new AreaOp.NZWindOp();
		}
		return operator.calculate(curves, EmptyCurves);
	}

	/**
	 * Adds the shape of the specified <code>Area</code> to the shape of this
	 * <code>Area</code>. The resulting shape of this <code>Area</code> will
	 * include the union of both shapes, or all areas that were contained in
	 * either this or the specified <code>Area</code>.
	 * 
	 * <pre>
	 *     // Example:
	 *     Area a1 = new Area([triangle 0,0 =&gt; 8,0 =&gt; 0,8]);
	 *     Area a2 = new Area([triangle 0,0 =&gt; 8,0 =&gt; 8,8]);
	 *     a1.add(a2);
	 * 
	 *        a1(before)     +         a2         =     a1(after)
	 * 
	 *     ################     ################     ################
	 *     ##############         ##############     ################
	 *     ############             ############     ################
	 *     ##########                 ##########     ################
	 *     ########                     ########     ################
	 *     ######                         ######     ######    ######
	 *     ####                             ####     ####        ####
	 *     ##                                 ##     ##            ##
	 * </pre>
	 * 
	 * @param rhs
	 *            the <code>Area</code> to be added to the current shape
	 * @throws NullPointerException
	 *             if <code>rhs</code> is null
	 * @since 1.2
	 */
	public void add(Area rhs) {
		curves = new AreaOp.AddOp().calculate(this.curves, rhs.curves);
		invalidateBounds();
	}

	/**
	 * Subtracts the shape of the specified <code>Area</code> from the shape of
	 * this <code>Area</code>. The resulting shape of this <code>Area</code>
	 * will include areas that were contained only in this <code>Area</code> and
	 * not in the specified <code>Area</code>.
	 * 
	 * <pre>
	 *     // Example:
	 *     Area a1 = new Area([triangle 0,0 =&gt; 8,0 =&gt; 0,8]);
	 *     Area a2 = new Area([triangle 0,0 =&gt; 8,0 =&gt; 8,8]);
	 *     a1.subtract(a2);
	 * 
	 *        a1(before)     -         a2         =     a1(after)
	 * 
	 *     ################     ################
	 *     ##############         ##############     ##
	 *     ############             ############     ####
	 *     ##########                 ##########     ######
	 *     ########                     ########     ########
	 *     ######                         ######     ######
	 *     ####                             ####     ####
	 *     ##                                 ##     ##
	 * </pre>
	 * 
	 * @param rhs
	 *            the <code>Area</code> to be subtracted from the current shape
	 * @throws NullPointerException
	 *             if <code>rhs</code> is null
	 * @since 1.2
	 */
	public void subtract(Area rhs) {
		curves = new AreaOp.SubOp().calculate(this.curves, rhs.curves);
		invalidateBounds();
	}

	/**
	 * Sets the shape of this <code>Area</code> to the intersection of its
	 * current shape and the shape of the specified <code>Area</code>. The
	 * resulting shape of this <code>Area</code> will include only areas that
	 * were contained in both this <code>Area</code> and also in the specified
	 * <code>Area</code>.
	 * 
	 * <pre>
	 *     // Example:
	 *     Area a1 = new Area([triangle 0,0 =&gt; 8,0 =&gt; 0,8]);
	 *     Area a2 = new Area([triangle 0,0 =&gt; 8,0 =&gt; 8,8]);
	 *     a1.intersect(a2);
	 * 
	 *      a1(before)   intersect     a2         =     a1(after)
	 * 
	 *     ################     ################     ################
	 *     ##############         ##############       ############
	 *     ############             ############         ########
	 *     ##########                 ##########           ####
	 *     ########                     ########
	 *     ######                         ######
	 *     ####                             ####
	 *     ##                                 ##
	 * </pre>
	 * 
	 * @param rhs
	 *            the <code>Area</code> to be intersected with this
	 *            <code>Area</code>
	 * @throws NullPointerException
	 *             if <code>rhs</code> is null
	 * @since 1.2
	 */
	public void intersect(Area rhs) {
		curves = new AreaOp.IntOp().calculate(this.curves, rhs.curves);
		invalidateBounds();
	}

	/**
	 * Sets the shape of this <code>Area</code> to be the combined area of its
	 * current shape and the shape of the specified <code>Area</code>, minus
	 * their intersection. The resulting shape of this <code>Area</code> will
	 * include only areas that were contained in either this <code>Area</code>
	 * or in the specified <code>Area</code>, but not in both.
	 * 
	 * <pre>
	 *     // Example:
	 *     Area a1 = new Area([triangle 0,0 =&gt; 8,0 =&gt; 0,8]);
	 *     Area a2 = new Area([triangle 0,0 =&gt; 8,0 =&gt; 8,8]);
	 *     a1.exclusiveOr(a2);
	 * 
	 *        a1(before)    xor        a2         =     a1(after)
	 * 
	 *     ################     ################
	 *     ##############         ##############     ##            ##
	 *     ############             ############     ####        ####
	 *     ##########                 ##########     ######    ######
	 *     ########                     ########     ################
	 *     ######                         ######     ######    ######
	 *     ####                             ####     ####        ####
	 *     ##                                 ##     ##            ##
	 * </pre>
	 * 
	 * @param rhs
	 *            the <code>Area</code> to be exclusive ORed with this
	 *            <code>Area</code>.
	 * @throws NullPointerException
	 *             if <code>rhs</code> is null
	 * @since 1.2
	 */
	public void exclusiveOr(Area rhs) {
		curves = new AreaOp.XorOp().calculate(this.curves, rhs.curves);
		invalidateBounds();
	}

	/**
	 * Removes all of the geometry from this <code>Area</code> and restores it
	 * to an empty area.
	 * 
	 * @since 1.2
	 */
	public void reset() {
		curves = new Vector();
		invalidateBounds();
	}

	/**
	 * Tests whether this <code>Area</code> object encloses any area.
	 * 
	 * @return <code>true</code> if this <code>Area</code> object represents an
	 *         empty area; <code>false</code> otherwise.
	 * @since 1.2
	 */
	public boolean isEmpty() {
		return (curves.size() == 0);
	}

	/**
	 * Tests whether this <code>Area</code> consists entirely of straight edged
	 * polygonal geometry.
	 * 
	 * @return <code>true</code> if the geometry of this <code>Area</code>
	 *         consists entirely of line segments; <code>false</code> otherwise.
	 * @since 1.2
	 */
	public boolean isPolygonal() {
		Enumeration enum_ = curves.elements();
		while (enum_.hasMoreElements()) {
			if (((Curve) enum_.nextElement()).getOrder() > 1) {
				return false;
			}
		}
		return true;
	}

	/**
	 * Tests whether this <code>Area</code> is rectangular in shape.
	 * 
	 * @return <code>true</code> if the geometry of this <code>Area</code> is
	 *         rectangular in shape; <code>false</code> otherwise.
	 * @since 1.2
	 */
	public boolean isRectangular() {
		int size = curves.size();
		if (size == 0) {
			return true;
		}
		if (size > 3) {
			return false;
		}
		Curve c1 = (Curve) curves.get(1);
		Curve c2 = (Curve) curves.get(2);
		if (c1.getOrder() != 1 || c2.getOrder() != 1) {
			return false;
		}
		if (c1.getXTop() != c1.getXBot() || c2.getXTop() != c2.getXBot()) {
			return false;
		}
		if (c1.getYTop() != c2.getYTop() || c1.getYBot() != c2.getYBot()) {
			// One might be able to prove that this is impossible...
			return false;
		}
		return true;
	}

	/**
	 * Tests whether this <code>Area</code> is comprised of a single closed
	 * subpath. This method returns <code>true</code> if the path contains 0 or
	 * 1 subpaths, or <code>false</code> if the path contains more than 1
	 * subpath. The subpaths are counted by the number of
	 * {@link PathIterator#SEG_MOVETO SEG_MOVETO} segments that appear in the
	 * path.
	 * 
	 * @return <code>true</code> if the <code>Area</code> is comprised of a
	 *         single basic geometry; <code>false</code> otherwise.
	 * @since 1.2
	 */
	public boolean isSingular() {
		if (curves.size() < 3) {
			return true;
		}
		Enumeration enum_ = curves.elements();
		enum_.nextElement(); // First Order0 "moveto"
		while (enum_.hasMoreElements()) {
			if (((Curve) enum_.nextElement()).getOrder() == 0) {
				return false;
			}
		}
		return true;
	}

	private Rectangle2D cachedBounds;

	private void invalidateBounds() {
		cachedBounds = null;
	}

	private Rectangle2D getCachedBounds() {
		if (cachedBounds != null) {
			return cachedBounds;
		}
		Rectangle2D r = new Rectangle2D.Double();
		if (curves.size() > 0) {
			Curve c = (Curve) curves.get(0);
			// First point is always an order 0 curve (moveto)
			r.setRect(c.getX0(), c.getY0(), 0, 0);
			for (int i = 1; i < curves.size(); i++) {
				((Curve) curves.get(i)).enlarge(r);
			}
		}
		return (cachedBounds = r);
	}

	/**
	 * Returns a high precision bounding {@link Rectangle2D} that completely
	 * encloses this <code>Area</code>.
	 * <p>
	 * The Area class will attempt to return the tightest bounding box possible
	 * for the Shape. The bounding box will not be padded to include the control
	 * points of curves in the outline of the Shape, but should tightly fit the
	 * actual geometry of the outline itself.
	 * 
	 * @return the bounding <code>Rectangle2D</code> for the <code>Area</code>.
	 * @since 1.2
	 */
	public Rectangle2D getBounds2D() {
		return getCachedBounds().getBounds2D();
	}

	/**
	 * Returns a bounding {@link Rectangle} that completely encloses this
	 * <code>Area</code>.
	 * <p>
	 * The Area class will attempt to return the tightest bounding box possible
	 * for the Shape. The bounding box will not be padded to include the control
	 * points of curves in the outline of the Shape, but should tightly fit the
	 * actual geometry of the outline itself. Since the returned object
	 * represents the bounding box with integers, the bounding box can only be
	 * as tight as the nearest integer coordinates that encompass the geometry
	 * of the Shape.
	 * 
	 * @return the bounding <code>Rectangle</code> for the <code>Area</code>.
	 * @since 1.2
	 */
	public Rectangle getBounds() {
		return getCachedBounds().getBounds();
	}

	/**
	 * Returns an exact copy of this <code>Area</code> object.
	 * 
	 * @return Created clone object
	 * @since 1.2
	 */
	public Object clone() {
		return new Area(this);
	}

	/**
	 * Tests whether the geometries of the two <code>Area</code> objects are
	 * equal. This method will return false if the argument is null.
	 * 
	 * @param other
	 *            the <code>Area</code> to be compared to this <code>Area</code>
	 * @return <code>true</code> if the two geometries are equal;
	 *         <code>false</code> otherwise.
	 * @since 1.2
	 */
	public boolean equals(Area other) {
		// REMIND: A *much* simpler operation should be possible...
		// Should be able to do a curve-wise comparison since all Areas
		// should evaluate their curves in the same top-down order.
		if (other == this) {
			return true;
		}
		if (other == null) {
			return false;
		}
		Vector c = new AreaOp.XorOp().calculate(this.curves, other.curves);
		return c.isEmpty();
	}

	/**
	 * Transforms the geometry of this <code>Area</code> using the specified
	 * {@link AffineTransform}. The geometry is transformed in place, which
	 * permanently changes the enclosed area defined by this object.
	 * 
	 * @param t
	 *            the transformation used to transform the area
	 * @throws NullPointerException
	 *             if <code>t</code> is null
	 * @since 1.2
	 */
	public void transform(AffineTransform t) {
		if (t == null) {
			throw new NullPointerException("transform must not be null");
		}
		// REMIND: A simpler operation can be performed for some types
		// of transform.
		curves = pathToCurves(getPathIterator(t));
		invalidateBounds();
	}

	/**
	 * Creates a new <code>Area</code> object that contains the same geometry as
	 * this <code>Area</code> transformed by the specified
	 * <code>AffineTransform</code>. This <code>Area</code> object is unchanged.
	 * 
	 * @param t
	 *            the specified <code>AffineTransform</code> used to transform
	 *            the new <code>Area</code>
	 * @throws NullPointerException
	 *             if <code>t</code> is null
	 * @return a new <code>Area</code> object representing the transformed
	 *         geometry.
	 * @since 1.2
	 */
	public Area createTransformedArea(AffineTransform t) {
		Area a = new Area(this);
		a.transform(t);
		return a;
	}

	/**
	 * {@inheritDoc}
	 * 
	 * @since 1.2
	 */
	public boolean contains(double x, double y) {
		if (!getCachedBounds().contains(x, y)) {
			return false;
		}
		Enumeration enum_ = curves.elements();
		int crossings = 0;
		while (enum_.hasMoreElements()) {
			Curve c = (Curve) enum_.nextElement();
			crossings += c.crossingsFor(x, y);
		}
		return ((crossings & 1) == 1);
	}

	/**
	 * {@inheritDoc}
	 * 
	 * @since 1.2
	 */
	public boolean contains(Point2D p) {
		return contains(p.getX(), p.getY());
	}

	/**
	 * {@inheritDoc}
	 * 
	 * @since 1.2
	 */
	public boolean contains(double x, double y, double w, double h) {
		if (w < 0 || h < 0) {
			return false;
		}
		if (!getCachedBounds().contains(x, y, w, h)) {
			return false;
		}
		Crossings c = Crossings.findCrossings(curves, x, y, x + w, y + h);
		return (c != null && c.covers(y, y + h));
	}

	/**
	 * {@inheritDoc}
	 * 
	 * @since 1.2
	 */
	public boolean contains(Rectangle2D r) {
		return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight());
	}

	/**
	 * {@inheritDoc}
	 * 
	 * @since 1.2
	 */
	public boolean intersects(double x, double y, double w, double h) {
		if (w < 0 || h < 0) {
			return false;
		}
		if (!getCachedBounds().intersects(x, y, w, h)) {
			return false;
		}
		Crossings c = Crossings.findCrossings(curves, x, y, x + w, y + h);
		return (c == null || !c.isEmpty());
	}

	/**
	 * {@inheritDoc}
	 * 
	 * @since 1.2
	 */
	public boolean intersects(Rectangle2D r) {
		return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight());
	}

	/**
	 * Creates a {@link PathIterator} for the outline of this <code>Area</code>
	 * object. This <code>Area</code> object is unchanged.
	 * 
	 * @param at
	 *            an optional <code>AffineTransform</code> to be applied to the
	 *            coordinates as they are returned in the iteration, or
	 *            <code>null</code> if untransformed coordinates are desired
	 * @return the <code>PathIterator</code> object that returns the geometry of
	 *         the outline of this <code>Area</code>, one segment at a time.
	 * @since 1.2
	 */
	public PathIterator getPathIterator(AffineTransform at) {
		return new AreaIterator(curves, at);
	}

	/**
	 * Creates a <code>PathIterator</code> for the flattened outline of this
	 * <code>Area</code> object. Only uncurved path segments represented by the
	 * SEG_MOVETO, SEG_LINETO, and SEG_CLOSE point types are returned by the
	 * iterator. This <code>Area</code> object is unchanged.
	 * 
	 * @param at
	 *            an optional <code>AffineTransform</code> to be applied to the
	 *            coordinates as they are returned in the iteration, or
	 *            <code>null</code> if untransformed coordinates are desired
	 * @param flatness
	 *            the maximum amount that the control points for a given curve
	 *            can vary from colinear before a subdivided curve is replaced
	 *            by a straight line connecting the end points
	 * @return the <code>PathIterator</code> object that returns the geometry of
	 *         the outline of this <code>Area</code>, one segment at a time.
	 * @since 1.2
	 */
	public PathIterator getPathIterator(AffineTransform at, double flatness) {
		return new FlatteningPathIterator(getPathIterator(at), flatness);
	}
}

@SuppressWarnings({ "rawtypes" })
class AreaIterator implements PathIterator {
	private AffineTransform transform;
	private Vector curves;
	private int index;
	private Curve prevcurve;
	private Curve thiscurve;

	public AreaIterator(Vector curves, AffineTransform at) {
		this.curves = curves;
		this.transform = at;
		if (curves.size() >= 1) {
			thiscurve = (Curve) curves.get(0);
		}
	}

	public int getWindingRule() {
		// REMIND: Which is better, EVEN_ODD or NON_ZERO?
		// The paths calculated could be classified either way.
		// return WIND_EVEN_ODD;
		return WIND_NON_ZERO;
	}

	public boolean isDone() {
		return (prevcurve == null && thiscurve == null);
	}

	public void next() {
		if (prevcurve != null) {
			prevcurve = null;
		} else {
			prevcurve = thiscurve;
			index++;
			if (index < curves.size()) {
				thiscurve = (Curve) curves.get(index);
				if (thiscurve.getOrder() != 0
						&& prevcurve.getX1() == thiscurve.getX0()
						&& prevcurve.getY1() == thiscurve.getY0()) {
					prevcurve = null;
				}
			} else {
				thiscurve = null;
			}
		}
	}

	public int currentSegment(float coords[]) {
		double dcoords[] = new double[6];
		int segtype = currentSegment(dcoords);
		int numpoints = (segtype == SEG_CLOSE ? 0 : (segtype == SEG_QUADTO ? 2
				: (segtype == SEG_CUBICTO ? 3 : 1)));
		for (int i = 0; i < numpoints * 2; i++) {
			coords[i] = (float) dcoords[i];
		}
		return segtype;
	}

	public int currentSegment(double coords[]) {
		int segtype;
		int numpoints;
		if (prevcurve != null) {
			// Need to finish off junction between curves
			if (thiscurve == null || thiscurve.getOrder() == 0) {
				return SEG_CLOSE;
			}
			coords[0] = thiscurve.getX0();
			coords[1] = thiscurve.getY0();
			segtype = SEG_LINETO;
			numpoints = 1;
		} else if (thiscurve == null) {
			throw new NoSuchElementException("area iterator out of bounds");
		} else {
			segtype = thiscurve.getSegment(coords);
			numpoints = thiscurve.getOrder();
			if (numpoints == 0) {
				numpoints = 1;
			}
		}
		if (transform != null) {
			transform.transform(coords, 0, coords, 0, numpoints);
		}
		return segtype;
	}
}
